package org.hhchat.leetcode.array;

public class code74_medium {
    static class Solution {
        public boolean searchMatrix(int[][] matrix, int target) {
            int m = matrix.length;
            if(m == 0 ){
                return false;
            }
            int n = matrix[0].length;
            if(n == 0){
                return false;
            }
            int arr[] = new int[matrix.length];
            for(int i = 0; i < matrix.length;i++) {
                arr[i] = matrix[i][0];
            }
            int index = binsearch(arr, target, 0, arr.length - 1);
            if (index >= 0 && matrix[index][0] == target) {
                return true;
            }else{
                if(index < 0)   {index = -(index + 1) -1 ;}
                if(index< 0 || index == m) return false;
                int indexC = binsearch(matrix[index], target, 0, matrix[index].length -1);
                if (indexC < 0) {
                    return false;
                }else{
                    return matrix[index][indexC] == target;
                }
            }
        }

        public int binsearch(int[] arr, int target, int start, int end){
            int l = start;
            int r = end;
            while(l<=r){
                int mid = (l + r) >>> 1;
                if(arr[mid] == target){
                    return mid;
                }else if(arr[mid] < target){
                    l = mid+1;
                }else{
                    r = mid - 1;
                }
            }
            return -(l+1);
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int arr[] = new int[]{1,3,7,9};
        int matrix[][] = new int[1][1];
        matrix[0] = new int[]{1};

        System.out.println(solution.searchMatrix(matrix, 0));
    }
}
